package ljl.alg.wangzheng_camp.round1.tree;

import commons.TreeNode;

import java.util.LinkedList;

public class _114_flatten_tree {
    
    /**
     * 前几天刚做的，毫无印象了
     * <p>
     * 背错了，妈的
     * 那个题是连成单链表，现在是，先根序遍历
     * <p>
     * 我去？居然过了
     * <p>
     * 我去？我才发现左要设置为 null，我没管，这个不对了
     * 好像本来就设置为 null 了，无意间
     * <p>
     * 我题都没搞明白就开始写，真王八蛋！
     */
    public void flatten(TreeNode root) {
        if (root == null) return;
        flatten(root.left);
        TreeNode left = root.left;
        root.left = null;
        
        flatten(root.right);
        TreeNode right = root.right;
        root.right = null;
        
        TreeNode leftRight = null;
        if (left != null) {
            leftRight = left;
            while (leftRight.right != null)
                leftRight = leftRight.right;
            root.right = left;
        }
        if (leftRight != null) {
            leftRight.right = right;
        } else {
            root.right = right;
        }
    }
    
    /**
     * 怎么没见有人用我那个解法？
     * 我和 labuladong 学的
     */
    public void flatten2(TreeNode root) {
        if (root == null) return;
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        TreeNode prev = null;
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            if (prev != null) {
                prev.left = null;
                prev.right = cur;
            }
            if (cur.right != null) stack.push(cur.right);
            if (cur.left != null) stack.push(cur.left);
            prev = cur;
        }
    }
    
    /**
     * 这个解法真的秒兄弟们，真的秒！
     * */
    public void flatten3(TreeNode root) {
        TreeNode cur = root;
        while (cur != null) {
            if (cur.left != null) {
                TreeNode next = cur.left;
                TreeNode pred = next;
                while (pred.right != null)
                    pred = pred.right;
                pred.right = cur.right;
                cur.left = null;
                cur.right = next;
            }
            cur = cur.right;
        }
    }
    
    
}
